<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
    "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<meta http-equiv="Content-Type" content="application/xhtml+xml; charset=UTF-8" />
<meta name="generator" content="AsciiDoc 8.6.8" />
<title>utlist: linked list macros for C structures</title>
<style type="text/css">
/* Shared CSS for AsciiDoc xhtml11 and html5 backends */

/* Default font. */
body {
  font-family: Georgia,serif;
}

/* Title font. */
h1, h2, h3, h4, h5, h6,
div.title, caption.title,
thead, p.table.header,
#toctitle,
#author, #revnumber, #revdate, #revremark,
#footer {
  font-family: Arial,Helvetica,sans-serif;
}

body {
  margin: 1em 5% 1em 5%;
}

a {
  color: blue;
  text-decoration: underline;
}
a:visited {
  color: fuchsia;
}

em {
  font-style: italic;
  color: navy;
}

strong {
  font-weight: bold;
  color: #083194;
}

h1, h2, h3, h4, h5, h6 {
  color: #527bbd;
  margin-top: 1.2em;
  margin-bottom: 0.5em;
  line-height: 1.3;
}

h1, h2, h3 {
  border-bottom: 2px solid silver;
}
h2 {
  padding-top: 0.5em;
}
h3 {
  float: left;
}
h3 + * {
  clear: left;
}
h5 {
  font-size: 1.0em;
}

div.sectionbody {
  margin-left: 0;
}

hr {
  border: 1px solid silver;
}

p {
  margin-top: 0.5em;
  margin-bottom: 0.5em;
}

ul, ol, li > p {
  margin-top: 0;
}
ul > li     { color: #aaa; }
ul > li > * { color: black; }

.monospaced, code, pre {
  font-family: "Courier New", Courier, monospace;
  font-size: inherit;
  color: navy;
  padding: 0;
  margin: 0;
}


#author {
  color: #527bbd;
  font-weight: bold;
  font-size: 1.1em;
}
#email {
}
#revnumber, #revdate, #revremark {
}

#footer {
  font-size: small;
  border-top: 2px solid silver;
  padding-top: 0.5em;
  margin-top: 4.0em;
}
#footer-text {
  float: left;
  padding-bottom: 0.5em;
}
#footer-badges {
  float: right;
  padding-bottom: 0.5em;
}

#preamble {
  margin-top: 1.5em;
  margin-bottom: 1.5em;
}
div.imageblock, div.exampleblock, div.verseblock,
div.quoteblock, div.literalblock, div.listingblock, div.sidebarblock,
div.admonitionblock {
  margin-top: 1.0em;
  margin-bottom: 1.5em;
}
div.admonitionblock {
  margin-top: 2.0em;
  margin-bottom: 2.0em;
  margin-right: 10%;
  color: #606060;
}

div.content { /* Block element content. */
  padding: 0;
}

/* Block element titles. */
div.title, caption.title {
  color: #527bbd;
  font-weight: bold;
  text-align: left;
  margin-top: 1.0em;
  margin-bottom: 0.5em;
}
div.title + * {
  margin-top: 0;
}

td div.title:first-child {
  margin-top: 0.0em;
}
div.content div.title:first-child {
  margin-top: 0.0em;
}
div.content + div.title {
  margin-top: 0.0em;
}

div.sidebarblock > div.content {
  background: #ffffee;
  border: 1px solid #dddddd;
  border-left: 4px solid #f0f0f0;
  padding: 0.5em;
}

div.listingblock > div.content {
  border: 1px solid #dddddd;
  border-left: 5px solid #f0f0f0;
  background: #f8f8f8;
  padding: 0.5em;
}

div.quoteblock, div.verseblock {
  padding-left: 1.0em;
  margin-left: 1.0em;
  margin-right: 10%;
  border-left: 5px solid #f0f0f0;
  color: #888;
}

div.quoteblock > div.attribution {
  padding-top: 0.5em;
  text-align: right;
}

div.verseblock > pre.content {
  font-family: inherit;
  font-size: inherit;
}
div.verseblock > div.attribution {
  padding-top: 0.75em;
  text-align: left;
}
/* DEPRECATED: Pre version 8.2.7 verse style literal block. */
div.verseblock + div.attribution {
  text-align: left;
}

div.admonitionblock .icon {
  vertical-align: top;
  font-size: 1.1em;
  font-weight: bold;
  text-decoration: underline;
  color: #527bbd;
  padding-right: 0.5em;
}
div.admonitionblock td.content {
  padding-left: 0.5em;
  border-left: 3px solid #dddddd;
}

div.exampleblock > div.content {
  border-left: 3px solid #dddddd;
  padding-left: 0.5em;
}

div.imageblock div.content { padding-left: 0; }
span.image img { border-style: none; vertical-align: text-bottom; }
a.image:visited { color: white; }

dl {
  margin-top: 0.8em;
  margin-bottom: 0.8em;
}
dt {
  margin-top: 0.5em;
  margin-bottom: 0;
  font-style: normal;
  color: navy;
}
dd > *:first-child {
  margin-top: 0.1em;
}

ul, ol {
    list-style-position: outside;
}
ol.arabic {
  list-style-type: decimal;
}
ol.loweralpha {
  list-style-type: lower-alpha;
}
ol.upperalpha {
  list-style-type: upper-alpha;
}
ol.lowerroman {
  list-style-type: lower-roman;
}
ol.upperroman {
  list-style-type: upper-roman;
}

div.compact ul, div.compact ol,
div.compact p, div.compact p,
div.compact div, div.compact div {
  margin-top: 0.1em;
  margin-bottom: 0.1em;
}

tfoot {
  font-weight: bold;
}
td > div.verse {
  white-space: pre;
}

div.hdlist {
  margin-top: 0.8em;
  margin-bottom: 0.8em;
}
div.hdlist tr {
  padding-bottom: 15px;
}
dt.hdlist1.strong, td.hdlist1.strong {
  font-weight: bold;
}
td.hdlist1 {
  vertical-align: top;
  font-style: normal;
  padding-right: 0.8em;
  color: navy;
}
td.hdlist2 {
  vertical-align: top;
}
div.hdlist.compact tr {
  margin: 0;
  padding-bottom: 0;
}

.comment {
  background: yellow;
}

.footnote, .footnoteref {
  font-size: 0.8em;
}

span.footnote, span.footnoteref {
  vertical-align: super;
}

#footnotes {
  margin: 20px 0 20px 0;
  padding: 7px 0 0 0;
}

#footnotes div.footnote {
  margin: 0 0 5px 0;
}

#footnotes hr {
  border: none;
  border-top: 1px solid silver;
  height: 1px;
  text-align: left;
  margin-left: 0;
  width: 20%;
  min-width: 100px;
}

div.colist td {
  padding-right: 0.5em;
  padding-bottom: 0.3em;
  vertical-align: top;
}
div.colist td img {
  margin-top: 0.3em;
}

@media print {
  #footer-badges { display: none; }
}

#toc {
  margin-bottom: 2.5em;
}

#toctitle {
  color: #527bbd;
  font-size: 1.1em;
  font-weight: bold;
  margin-top: 1.0em;
  margin-bottom: 0.1em;
}

div.toclevel0, div.toclevel1, div.toclevel2, div.toclevel3, div.toclevel4 {
  margin-top: 0;
  margin-bottom: 0;
}
div.toclevel2 {
  margin-left: 2em;
  font-size: 0.9em;
}
div.toclevel3 {
  margin-left: 4em;
  font-size: 0.9em;
}
div.toclevel4 {
  margin-left: 6em;
  font-size: 0.9em;
}

span.aqua { color: aqua; }
span.black { color: black; }
span.blue { color: blue; }
span.fuchsia { color: fuchsia; }
span.gray { color: gray; }
span.green { color: green; }
span.lime { color: lime; }
span.maroon { color: maroon; }
span.navy { color: navy; }
span.olive { color: olive; }
span.purple { color: purple; }
span.red { color: red; }
span.silver { color: silver; }
span.teal { color: teal; }
span.white { color: white; }
span.yellow { color: yellow; }

span.aqua-background { background: aqua; }
span.black-background { background: black; }
span.blue-background { background: blue; }
span.fuchsia-background { background: fuchsia; }
span.gray-background { background: gray; }
span.green-background { background: green; }
span.lime-background { background: lime; }
span.maroon-background { background: maroon; }
span.navy-background { background: navy; }
span.olive-background { background: olive; }
span.purple-background { background: purple; }
span.red-background { background: red; }
span.silver-background { background: silver; }
span.teal-background { background: teal; }
span.white-background { background: white; }
span.yellow-background { background: yellow; }

span.big { font-size: 2em; }
span.small { font-size: 0.6em; }

span.underline { text-decoration: underline; }
span.overline { text-decoration: overline; }
span.line-through { text-decoration: line-through; }

div.unbreakable { page-break-inside: avoid; }


/*
 * xhtml11 specific
 *
 * */

div.tableblock {
  margin-top: 1.0em;
  margin-bottom: 1.5em;
}
div.tableblock > table {
  border: 3px solid #527bbd;
}
thead, p.table.header {
  font-weight: bold;
  color: #527bbd;
}
p.table {
  margin-top: 0;
}
/* Because the table frame attribute is overriden by CSS in most browsers. */
div.tableblock > table[frame="void"] {
  border-style: none;
}
div.tableblock > table[frame="hsides"] {
  border-left-style: none;
  border-right-style: none;
}
div.tableblock > table[frame="vsides"] {
  border-top-style: none;
  border-bottom-style: none;
}


/*
 * html5 specific
 *
 * */

table.tableblock {
  margin-top: 1.0em;
  margin-bottom: 1.5em;
}
thead, p.tableblock.header {
  font-weight: bold;
  color: #527bbd;
}
p.tableblock {
  margin-top: 0;
}
table.tableblock {
  border-width: 3px;
  border-spacing: 0px;
  border-style: solid;
  border-color: #527bbd;
  border-collapse: collapse;
}
th.tableblock, td.tableblock {
  border-width: 1px;
  padding: 4px;
  border-style: solid;
  border-color: #527bbd;
}

table.tableblock.frame-topbot {
  border-left-style: hidden;
  border-right-style: hidden;
}
table.tableblock.frame-sides {
  border-top-style: hidden;
  border-bottom-style: hidden;
}
table.tableblock.frame-none {
  border-style: hidden;
}

th.tableblock.halign-left, td.tableblock.halign-left {
  text-align: left;
}
th.tableblock.halign-center, td.tableblock.halign-center {
  text-align: center;
}
th.tableblock.halign-right, td.tableblock.halign-right {
  text-align: right;
}

th.tableblock.valign-top, td.tableblock.valign-top {
  vertical-align: top;
}
th.tableblock.valign-middle, td.tableblock.valign-middle {
  vertical-align: middle;
}
th.tableblock.valign-bottom, td.tableblock.valign-bottom {
  vertical-align: bottom;
}


/*
 * manpage specific
 *
 * */

body.manpage h1 {
  padding-top: 0.5em;
  padding-bottom: 0.5em;
  border-top: 2px solid silver;
  border-bottom: 2px solid silver;
}
body.manpage h2 {
  border-style: none;
}
body.manpage div.sectionbody {
  margin-left: 3em;
}

@media print {
  body.manpage div#toc { display: none; }
}


@media screen {
  body {
    max-width: 50em; /* approximately 80 characters wide */
    margin-left: 16em;
  }

  #toc {
    position: fixed;
    top: 0;
    left: 0;
    bottom: 0;
    width: 13em;
    padding: 0.5em;
    padding-bottom: 1.5em;
    margin: 0;
    overflow: auto;
    border-right: 3px solid #f8f8f8;
    background-color: white;
  }

  #toc .toclevel1 {
    margin-top: 0.5em;
  }

  #toc .toclevel2 {
    margin-top: 0.25em;
    display: list-item;
    color: #aaaaaa;
  }

  #toctitle {
    margin-top: 0.5em;
  }
}
</style>
<script type="text/javascript">
/*<![CDATA[*/
var asciidoc = {  // Namespace.

/////////////////////////////////////////////////////////////////////
// Table Of Contents generator
/////////////////////////////////////////////////////////////////////

/* Author: Mihai Bazon, September 2002
 * http://students.infoiasi.ro/~mishoo
 *
 * Table Of Content generator
 * Version: 0.4
 *
 * Feel free to use this script under the terms of the GNU General Public
 * License, as long as you do not remove or alter this notice.
 */

 /* modified by Troy D. Hanson, September 2006. License: GPL */
 /* modified by Stuart Rackham, 2006, 2009. License: GPL */

// toclevels = 1..4.
toc: function (toclevels) {

  function getText(el) {
    var text = "";
    for (var i = el.firstChild; i != null; i = i.nextSibling) {
      if (i.nodeType == 3 /* Node.TEXT_NODE */) // IE doesn't speak constants.
        text += i.data;
      else if (i.firstChild != null)
        text += getText(i);
    }
    return text;
  }

  function TocEntry(el, text, toclevel) {
    this.element = el;
    this.text = text;
    this.toclevel = toclevel;
  }

  function tocEntries(el, toclevels) {
    var result = new Array;
    var re = new RegExp('[hH]([1-'+(toclevels+1)+'])');
    // Function that scans the DOM tree for header elements (the DOM2
    // nodeIterator API would be a better technique but not supported by all
    // browsers).
    var iterate = function (el) {
      for (var i = el.firstChild; i != null; i = i.nextSibling) {
        if (i.nodeType == 1 /* Node.ELEMENT_NODE */) {
          var mo = re.exec(i.tagName);
          if (mo && (i.getAttribute("class") || i.getAttribute("className")) != "float") {
            result[result.length] = new TocEntry(i, getText(i), mo[1]-1);
          }
          iterate(i);
        }
      }
    }
    iterate(el);
    return result;
  }

  var toc = document.getElementById("toc");
  if (!toc) {
    return;
  }

  // Delete existing TOC entries in case we're reloading the TOC.
  var tocEntriesToRemove = [];
  var i;
  for (i = 0; i < toc.childNodes.length; i++) {
    var entry = toc.childNodes[i];
    if (entry.nodeName.toLowerCase() == 'div'
     && entry.getAttribute("class")
     && entry.getAttribute("class").match(/^toclevel/))
      tocEntriesToRemove.push(entry);
  }
  for (i = 0; i < tocEntriesToRemove.length; i++) {
    toc.removeChild(tocEntriesToRemove[i]);
  }

  // Rebuild TOC entries.
  var entries = tocEntries(document.getElementById("content"), toclevels);
  for (var i = 0; i < entries.length; ++i) {
    var entry = entries[i];
    if (entry.element.id == "")
      entry.element.id = "_toc_" + i;
    var a = document.createElement("a");
    a.href = "#" + entry.element.id;
    a.appendChild(document.createTextNode(entry.text));
    var div = document.createElement("div");
    div.appendChild(a);
    div.className = "toclevel" + entry.toclevel;
    toc.appendChild(div);
  }
  if (entries.length == 0)
    toc.parentNode.removeChild(toc);
},


/////////////////////////////////////////////////////////////////////
// Footnotes generator
/////////////////////////////////////////////////////////////////////

/* Based on footnote generation code from:
 * http://www.brandspankingnew.net/archive/2005/07/format_footnote.html
 */

footnotes: function () {
  // Delete existing footnote entries in case we're reloading the footnodes.
  var i;
  var noteholder = document.getElementById("footnotes");
  if (!noteholder) {
    return;
  }
  var entriesToRemove = [];
  for (i = 0; i < noteholder.childNodes.length; i++) {
    var entry = noteholder.childNodes[i];
    if (entry.nodeName.toLowerCase() == 'div' && entry.getAttribute("class") == "footnote")
      entriesToRemove.push(entry);
  }
  for (i = 0; i < entriesToRemove.length; i++) {
    noteholder.removeChild(entriesToRemove[i]);
  }

  // Rebuild footnote entries.
  var cont = document.getElementById("content");
  var spans = cont.getElementsByTagName("span");
  var refs = {};
  var n = 0;
  for (i=0; i<spans.length; i++) {
    if (spans[i].className == "footnote") {
      n++;
      var note = spans[i].getAttribute("data-note");
      if (!note) {
        // Use [\s\S] in place of . so multi-line matches work.
        // Because JavaScript has no s (dotall) regex flag.
        note = spans[i].innerHTML.match(/\s*\[([\s\S]*)]\s*/)[1];
        spans[i].innerHTML =
          "[<a id='_footnoteref_" + n + "' href='#_footnote_" + n +
          "' title='View footnote' class='footnote'>" + n + "</a>]";
        spans[i].setAttribute("data-note", note);
      }
      noteholder.innerHTML +=
        "<div class='footnote' id='_footnote_" + n + "'>" +
        "<a href='#_footnoteref_" + n + "' title='Return to text'>" +
        n + "</a>. " + note + "</div>";
      var id =spans[i].getAttribute("id");
      if (id != null) refs["#"+id] = n;
    }
  }
  if (n == 0)
    noteholder.parentNode.removeChild(noteholder);
  else {
    // Process footnoterefs.
    for (i=0; i<spans.length; i++) {
      if (spans[i].className == "footnoteref") {
        var href = spans[i].getElementsByTagName("a")[0].getAttribute("href");
        href = href.match(/#.*/)[0];  // Because IE return full URL.
        n = refs[href];
        spans[i].innerHTML =
          "[<a href='#_footnote_" + n +
          "' title='View footnote' class='footnote'>" + n + "</a>]";
      }
    }
  }
},

install: function(toclevels) {
  var timerId;

  function reinstall() {
    asciidoc.footnotes();
    if (toclevels) {
      asciidoc.toc(toclevels);
    }
  }

  function reinstallAndRemoveTimer() {
    clearInterval(timerId);
    reinstall();
  }

  timerId = setInterval(reinstall, 500);
  if (document.addEventListener)
    document.addEventListener("DOMContentLoaded", reinstallAndRemoveTimer, false);
  else
    window.onload = reinstallAndRemoveTimer;
}

}
asciidoc.install(2);
/*]]>*/
</script>
</head>
<body class="article">
<div id="header">
<h1>utlist: linked list macros for C structures</h1>
<span id="author">Troy D. Hanson</span><br />
<span id="email"><code>&lt;<a href="mailto:tdh@tkhanson.net">tdh@tkhanson.net</a>&gt;</code></span><br />
<span id="revnumber">version 1.9.8,</span>
<span id="revdate">March 2013</span>
<div id="toc">
  <div id="toctitle">Table of Contents</div>
  <noscript><p><b>JavaScript must be enabled in your browser to display the table of contents.</b></p></noscript>
</div>
</div>
<div id="content">
<div id="preamble">
<div class="sectionbody">
<div class="paragraph"><p>Here&#8217;s a link back to the <a href="https://github.com/troydhanson/uthash">GitHub project page</a>.</p></div>
</div>
</div>
<div class="sect1">
<h2 id="_introduction">Introduction</h2>
<div class="sectionbody">
<div class="paragraph"><p>A set of general-purpose <em>linked list</em> macros for C structures are included with
uthash in <code>utlist.h</code>.  To use these macros in your own C program, just
copy <code>utlist.h</code> into your source directory and use it in your programs.</p></div>
<div class="literalblock">
<div class="content">
<pre><code>#include "utlist.h"</code></pre>
</div></div>
<div class="paragraph"><p>These macros support the basic linked list operations: adding and deleting
elements, sorting them and iterating over them.</p></div>
<div class="sect2">
<h3 id="_download">Download</h3>
<div class="paragraph"><p>To download the <code>utlist.h</code> header file,
follow the links on <a href="https://github.com/troydhanson/uthash">https://github.com/troydhanson/uthash</a> to clone uthash or get a zip file,
then look in the src/ sub-directory.</p></div>
</div>
<div class="sect2">
<h3 id="_bsd_licensed">BSD licensed</h3>
<div class="paragraph"><p>This software is made available under the
<a href="license.html">revised BSD license</a>.
It is free and open source.</p></div>
</div>
<div class="sect2">
<h3 id="_platforms">Platforms</h3>
<div class="paragraph"><p>The <em>utlist</em> macros have been tested on:</p></div>
<div class="ulist"><ul>
<li>
<p>
Linux,
</p>
</li>
<li>
<p>
Mac OS X, and
</p>
</li>
<li>
<p>
Windows, using Visual Studio 2008, Visual Studio 2010, or Cygwin/MinGW.
</p>
</li>
</ul></div>
</div>
</div>
</div>
<div class="sect1">
<h2 id="_using_utlist">Using utlist</h2>
<div class="sectionbody">
<div class="sect2">
<h3 id="_types_of_lists">Types of lists</h3>
<div class="paragraph"><p>Three types of linked lists are supported:</p></div>
<div class="ulist"><ul>
<li>
<p>
<strong>singly-linked</strong> lists,
</p>
</li>
<li>
<p>
<strong>doubly-linked</strong> lists, and
</p>
</li>
<li>
<p>
<strong>circular, doubly-linked</strong> lists
</p>
</li>
</ul></div>
<div class="sect3">
<h4 id="_efficiency">Efficiency</h4>
<div class="paragraph"><p>For all types of lists, prepending elements and deleting elements are
constant-time operations. Appending to a singly-linked list is an <em>O(n)</em>
operation but appending to a doubly-linked list is constant time using these
macros.  (This is because, in the utlist implementation of the doubly-linked
list, the head element&#8217;s <code>prev</code> member points back to the list tail, even when
the list is non-circular). Sorting is an <em>O(n log(n))</em> operation. Iteration
and searching are <code>O(n)</code> for all list types.</p></div>
</div>
</div>
<div class="sect2">
<h3 id="_list_elements">List elements</h3>
<div class="paragraph"><p>You can use any structure with these macros, as long as the structure
contains a <code>next</code> pointer. If you want to make a doubly-linked list,
the element also needs to have a <code>prev</code> pointer.</p></div>
<div class="literalblock">
<div class="content">
<pre><code>typedef struct element {
    char *name;
    struct element *prev; /* needed for a doubly-linked list only */
    struct element *next; /* needed for singly- or doubly-linked lists */
} element;</code></pre>
</div></div>
<div class="paragraph"><p>You can name your structure anything. In the example above it is called <code>element</code>.
Within a particular list, all elements must be of the same type.</p></div>
<div class="sect3">
<h4 id="_flexible_prev_next_naming">Flexible prev/next naming</h4>
<div class="paragraph"><p>You can name your <code>prev</code> and <code>next</code> pointers something else. If you do, there is
a <a href="#flex_names">family of macros</a> that work identically but take these names as
extra arguments.</p></div>
</div>
</div>
<div class="sect2">
<h3 id="_list_head">List head</h3>
<div class="paragraph"><p>The list head is simply a pointer to your element structure. You can name it
anything. <strong>It must be initialized to <code>NULL</code></strong>.</p></div>
<div class="literalblock">
<div class="content">
<pre><code>element *head = NULL;</code></pre>
</div></div>
</div>
<div class="sect2">
<h3 id="_list_operations">List operations</h3>
<div class="paragraph"><p>The lists support inserting or deleting elements, sorting the elements and
iterating over them.</p></div>
<div class="tableblock">
<table rules="cols"
width="100%"
frame="border"
cellspacing="0" cellpadding="4">
<col width="33%" />
<col width="33%" />
<col width="33%" />
<thead>
<tr>
<th align="left" valign="top">Singly-linked             </th>
<th align="left" valign="top"> Doubly-linked              </th>
<th align="left" valign="top"> Circular, doubly-linked</th>
</tr>
</thead>
<tbody>
<tr>
<td align="left" valign="top"><p class="table"><code>LL_PREPEND(head,add);</code></p></td>
<td align="left" valign="top"><p class="table"><code>DL_PREPEND(head,add);</code></p></td>
<td align="left" valign="top"><p class="table"><code>CDL_PREPEND(head,add;</code></p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><code>LL_PREPEND_ELEM(head,elt,add)</code></p></td>
<td align="left" valign="top"><p class="table"><code>DL_PREPEND_ELEM(head,elt,add)</code></p></td>
<td align="left" valign="top"><p class="table"><code>CDL_PREPEND_ELEM(head,elt,add)</code></p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><code>LL_REPLACE_ELEM(head,elt,add)</code></p></td>
<td align="left" valign="top"><p class="table"><code>DL_REPLACE_ELEM(head,elt,add)</code></p></td>
<td align="left" valign="top"><p class="table"><code>CDL_REPLACE_ELEM(head,elt,add)</code></p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><code>LL_APPEND(head,add);</code></p></td>
<td align="left" valign="top"><p class="table"><code>DL_APPEND(head,add);</code></p></td>
<td align="left" valign="top"><p class="table"><code></code></p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><code>LL_CONCAT(head1,head2);</code></p></td>
<td align="left" valign="top"><p class="table"><code>DL_CONCAT(head1,head2);</code></p></td>
<td align="left" valign="top"><p class="table"><code></code></p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><code>LL_DELETE(head,del);</code></p></td>
<td align="left" valign="top"><p class="table"><code>DL_DELETE(head,del);</code></p></td>
<td align="left" valign="top"><p class="table"><code>CDL_DELETE(head,del);</code></p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><code>LL_SORT(head,cmp);</code></p></td>
<td align="left" valign="top"><p class="table"><code>DL_SORT(head,cmp);</code></p></td>
<td align="left" valign="top"><p class="table"><code>CDL_SORT(head,cmp);</code></p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><code>LL_FOREACH(head,elt) {&#8230;}</code></p></td>
<td align="left" valign="top"><p class="table"><code>DL_FOREACH(head,elt) {&#8230;}</code></p></td>
<td align="left" valign="top"><p class="table"><code>CDL_FOREACH(head,elt) {&#8230;}</code></p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><code>LL_FOREACH_SAFE(head,elt,tmp) {&#8230;}</code></p></td>
<td align="left" valign="top"><p class="table"><code>DL_FOREACH_SAFE(head,elt,tmp) {&#8230;}</code></p></td>
<td align="left" valign="top"><p class="table"><code>CDL_FOREACH_SAFE(head,elt,tmp1,tmp2) {&#8230;}</code></p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><code>LL_SEARCH_SCALAR(head,elt,mbr,val);</code></p></td>
<td align="left" valign="top"><p class="table"><code>DL_SEARCH_SCALAR(head,elt,mbr,val);</code></p></td>
<td align="left" valign="top"><p class="table"><code>CDL_SEARCH_SCALAR(head,elt,mbr,val);</code></p></td>
</tr>
<tr>
<td align="left" valign="top"><p class="table"><code>LL_SEARCH(head,elt,like,cmp);</code></p></td>
<td align="left" valign="top"><p class="table"><code>DL_SEARCH(head,elt,like,cmp);</code></p></td>
<td align="left" valign="top"><p class="table"><code>CDL_SEARCH(head,elt,like,cmp);</code></p></td>
</tr>
</tbody>
</table>
</div>
<div class="paragraph"><p><em>Prepend</em> means to insert an element in front of the existing list head (if any),
changing the list head to the new element. <em>Append</em> means to add an element at the
end of the list, so it becomes the new tail element. <em>Concatenate</em> takes two
properly constructed lists and appends the second list to the first.  (Visual
Studio 2008 does not support <code>LL_CONCAT</code> and <code>DL_CONCAT</code>, but VS2010 is ok.)
To prepend before an arbitrary element instead of the list head, use the
<code>_PREPEND_ELEM</code> macro family. To <em>replace</em> an arbitary list element with another
element use the <code>_REPLACE_ELEM</code> family of macros.</p></div>
<div class="paragraph"><p>The <em>sort</em> operation never moves the elements in memory; rather it only adjusts
the list order by altering the <code>prev</code> and <code>next</code> pointers in each element. Also
the sort operation can change the list head to point to a new element.</p></div>
<div class="paragraph"><p>The <em>foreach</em> operation is for easy iteration over the list from the head to the
tail. A usage example is shown below. You can of course just use the <code>prev</code> and
<code>next</code> pointers directly instead of using the <em>foreach</em> macros.
The <em>foreach_safe</em> operation should be used if you plan to delete any of the list
elements while iterating.</p></div>
<div class="paragraph"><p>The <em>search</em> operation is a shortcut for iteration in search of a particular
element. It is not any faster than manually iterating and testing each element.
There are two forms: the "scalar" version searches for an element using a
simple equality test on a given structure member, while the general version takes an
element to which all others in the list will be compared using a <code>cmp</code> function.</p></div>
<div class="paragraph"><p>The parameters shown in the table above are explained here:</p></div>
<div class="dlist"><dl>
<dt class="hdlist1">
head
</dt>
<dd>
<p>
  The list head (a pointer to your list element structure).
</p>
</dd>
<dt class="hdlist1">
add
</dt>
<dd>
<p>
  A pointer to the list element structure you are adding to the list.
</p>
</dd>
<dt class="hdlist1">
del
</dt>
<dd>
<p>
  A pointer to the list element structure you are deleting from the list.
</p>
</dd>
<dt class="hdlist1">
elt
</dt>
<dd>
<p>
  A pointer that will be assigned to each list element in succession (see
  example) in the case of iteration macros; or, the output pointer from
  the search macros; or the element to be prepended to or replaced.
</p>
</dd>
<dt class="hdlist1">
like
</dt>
<dd>
<p>
  An element pointer, having the same type as <code>elt</code>, for which the search macro
  seeks a match (if found, the match is stored in <code>elt</code>). A match is determined
  by the given <code>cmp</code> function.
</p>
</dd>
<dt class="hdlist1">
cmp
</dt>
<dd>
<p>
  pointer to comparison function which accepts two arguments-- these are
  pointers to two element structures to be compared. The comparison function
  must return an <code>int</code> that is negative, zero, or positive, which specifies
  whether the first item should sort before, equal to, or after the second item,
  respectively. (In other words, the same convention that is used by <code>strcmp</code>).
  Note that under Visual Studio 2008 you may need to declare the two arguments
  as <code>void *</code> and then cast them back to their actual types.
</p>
</dd>
<dt class="hdlist1">
tmp
</dt>
<dd>
<p>
  A pointer of the same type as <code>elt</code>. Used internally. Need not be initialized.
</p>
</dd>
<dt class="hdlist1">
mbr
</dt>
<dd>
<p>
  In the scalar search macro, the name of a member within the <code>elt</code> structure which
  will be tested (using <code>==</code>) for equality with the value <code>val</code>.
</p>
</dd>
<dt class="hdlist1">
val
</dt>
<dd>
<p>
  In the scalar search macro, specifies the value of (of structure member
  <code>field</code>) of the element being sought.
</p>
</dd>
</dl></div>
</div>
<div class="sect2">
<h3 id="_example">Example</h3>
<div class="paragraph"><p>This example program reads names from a text file (one name per line), and
appends each name to a doubly-linked list. Then it sorts and prints them.</p></div>
<div class="listingblock">
<div class="title">A doubly-linked list</div>
<div class="content">
<pre><code>#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;string.h&gt;
#include "utlist.h"

#define BUFLEN 20

typedef struct el {
    char bname[BUFLEN];
    struct el *next, *prev;
} el;

int namecmp(el *a, el *b) {
    return strcmp(a-&gt;bname,b-&gt;bname);
}

el *head = NULL; /* important- initialize to NULL! */

int main(int argc, char *argv[]) {
    el *name, *elt, *tmp, etmp;

    char linebuf[BUFLEN];
    FILE *file;

    if ( (file = fopen( "test11.dat", "r" )) == NULL ) {
        perror("can't open: ");
        exit(-1);
    }

    while (fgets(linebuf,BUFLEN,file) != NULL) {
        if ( (name = (el*)malloc(sizeof(el))) == NULL) exit(-1);
        strncpy(name-&gt;bname,linebuf,BUFLEN);
        DL_APPEND(head, name);
    }
    DL_SORT(head, namecmp);
    DL_FOREACH(head,elt) printf("%s", elt-&gt;bname);

    memcpy(&amp;etmp.bname, "WES\n", 5);
    DL_SEARCH(head,elt,&amp;etmp,namecmp);
    if (elt) printf("found %s\n", elt-&gt;bname);

    /* now delete each element, use the safe iterator */
    DL_FOREACH_SAFE(head,elt,tmp) {
      DL_DELETE(head,elt);
    }

    fclose(file);

    return 0;
}</code></pre>
</div></div>
</div>
<div class="sect2">
<h3 id="flex_names">Other names for prev and next</h3>
<div class="paragraph"><p>If the <code>prev</code> and <code>next</code> fields are named something else, a separate group of
macros must be used. These work the same as the regular macros, but take the
field names as extra parameters.</p></div>
<div class="paragraph"><p>These "flexible field name" macros are shown below. They all end with "2". Each
operates the same as its counterpart without the 2, but they take the name of
the <code>prev</code> and <code>next</code> fields (as applicable) as trailing arguments.</p></div>
<div class="literalblock">
<div class="title">Flexible field name macros</div>
<div class="content">
<pre><code>LL_SORT2(list, cmp, next)
DL_SORT2(list, cmp, prev, next)
CDL_SORT2(list, cmp, prev, next)
LL_PREPEND2(head,add,next)
LL_CONCAT2(head1,head2,next)
LL_APPEND2(head,add,next)
LL_DELETE2(head,del,next)
LL_FOREACH2(head,el,next)
LL_FOREACH_SAFE2(head,el,tmp,next)
LL_SEARCH_SCALAR2(head,out,field,val,next)
LL_SEARCH2(head,out,elt,cmp,next)
DL_PREPEND2(head,add,prev,next)
DL_APPEND2(head,add,prev,next)
DL_CONCAT2(head1,head2,prev,next)
DL_DELETE2(head,del,prev,next)
DL_FOREACH2(head,el,next)
DL_FOREACH_SAFE2(head,el,tmp,next)
CDL_PREPEND2(head,add,prev,next)
CDL_DELETE2(head,del,prev,next)
CDL_FOREACH2(head,el,next)
CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next)
CDL_SEARCH_SCALAR2(head,out,field,val,next)
CDL_SEARCH2(head,out,elt,cmp,next)</code></pre>
</div></div>
</div>
</div>
</div>
</div>
<div id="footnotes"><hr /></div>
<div id="footer">
<div id="footer-text">
Version 1.9.8<br />
Last updated 2013-03-17 14:17:35 EDT
</div>
</div>
</body>
</html>
